package WeeklyContest;


import java.awt.*;
import java.util.*;
import java.util.List;

/**
 * @author:gao
 * @date:2020/7/12
 * @time:10:28
 * @version:0.0.1
 * @description:none
 */

public class W197 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int n=4;
        int[][] edges =new int[][]{
                {0,1},{1,2},{2,3},{3,0},{1,3}
        };
        double[] succProb = {0.5,0.1,0.3,0.2,0.8};
        int start =0;
        int end =2;
        double ans =solution.maxProbability(n,edges,succProb,start,end);
        System.out.println(ans);
    }

}

//5460. 好数对的数目
class Solution111 {
    public int numIdenticalPairs(int[] nums) {
        int ans=0;
        for (int i = 0; i <nums.length ; i++) {
            for (int j = i+1; j <nums.length ; j++) {
                if(nums[i]==nums[j]) ans++;
            }
        }
        return ans;
    }
}

//5461. 仅含 1 的子串数
class Solution32333 {
    public int numSub(String s) {
        int lastOneIndex =0;
        boolean isOne =false;
        int ans=0;
        int mod = (int) (1.0e9+7);
        for (int i = 0; i <s.length() ; i++) {
            if(s.charAt(i)=='1'){
                if(isOne==false){
                    isOne =true;
                    lastOneIndex = i;
                    ans=(ans+1)%mod;
                }else{//当前为True
                    ans = ((ans+i-lastOneIndex)%mod+1)%mod;
                }
            }else{//当前为0
                isOne = false;
            }
        }
        return ans;
    }
}

//5211. 概率最大的路径
//未优化得版本
class SolutionFive777 {

    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer, Double>[] m  =new Map[n];
        for (int i = 0; i <succProb.length; i++) {
            int endP = edges[i][1];
            int startP = edges[i][0];
            double prob = succProb[i];
            if(m[endP]==null){
                m[endP]= new HashMap<>();
            }
            if(m[startP]==null){
                m[startP] = new HashMap<>();
            }
            m[endP].put(startP,prob);
            m[startP].put(endP,prob);
        }
        boolean[] finished = new boolean[n];
        Arrays.fill(finished,false);
        double[] probV = new double[n];
        Arrays.fill(probV,-1.0);

        if(m[end]==null) return 0.0;
        //初始化
        for (Integer key:m[end].keySet()){
            double prob = m[end].get(key);
            probV[key]=prob;
        }
        for (int i = 0; i <n ; i++) {
            int index =-1;
            double maxPorb =-1;
            //找到最大得值
            for (int j = 0; j <n ; j++) {
                if(!finished[j]&&maxPorb<probV[j]){
                    index = j;
                    maxPorb = probV[j];
                }
            }
            if(maxPorb<=0) return finished[start]? probV[start]:0;
            if(index==start) return maxPorb;
            finished[index]=true;
            //更新距离
            if(m[index]!=null) {
                for (Integer key : m[index].keySet()) {
                    if (finished[key] == false) {
                        probV[key] =  Math.max(probV[key],probV[index]*m[index].get(key));
                    }
                }
            }
        }
        return probV[start];
    }
}


//bfs
class Solution333 {

    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {

        double error = 1e-6;
        Map<Integer, List<Node>> map = new HashMap<>();
        //把当前得结构放进去
        for (int i = 0; i < edges.length; i++) {
            int[] e = edges[i];
            if (!map.containsKey(e[0])) {
                map.put(e[0], new ArrayList<>());
            }

            if (!map.containsKey(e[1])) {
                map.put(e[1], new ArrayList<>());
            }
            map.get(e[0]).add(new Node(e[0], e[1], succProb[i]));
            map.get(e[1]).add(new Node(e[1], e[0], succProb[i]));
        }
        double[] dp = new double[n];
        dp[start] = 1;
        //BFS搜索
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        while (!q.isEmpty()) {
            int cur = q.poll();
            //找到以当前结点连接得点
            for (Node node : map.getOrDefault(cur, new ArrayList<>())) {
                //循环，看看能不能让成功率更高，如果成功率更高，就可以选用，
                //把点放入node
                if (dp[cur] * node.prob > dp[node.to] + error) {
                    q.add(node.to);
                    //保存当前点得成功率
                    dp[node.to] = dp[cur] * node.prob;
                }
            }
        }
        return dp[end];
    }

    class Node {
        int from;
        int to;
        double prob;
        public Node(int from, int to, double prob) {
            this.from = from;
            this.to = to;
            this.prob = prob;
        }
    }
}



//大根堆优化
class Point {
    int point;
    double prob;
    public  Point(int point0,double prob0){
        this.point = point0;
        prob = prob0;
    }

//        //实现大根堆
//        @Override
//        public int compareTo(Point o) {
//            return o.prob>this.prob?1:-1;
//        }
}

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer, Double>[] m  =new Map[n];
        for (int i = 0; i <succProb.length; i++) {
            int endP = edges[i][1];
            int startP = edges[i][0];
            double prob = succProb[i];
            if(m[endP]==null){
                m[endP]= new HashMap<>();
            }
            if(m[startP]==null){
                m[startP] = new HashMap<>();
            }
            m[endP].put(startP,prob);
            m[startP].put(endP,prob);
        }
        boolean[] finished = new boolean[n];
        Arrays.fill(finished,false);
        double[] probV = new double[n];
        PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return o1.prob>o2.prob?-1:1;
            }
        });
        Arrays.fill(probV,0.0);
        if(m[end]==null) return 0.0;
        //初始化
        for (Integer key:m[end].keySet()){
            double prob = m[end].get(key);
            probV[key]=prob;
            pq.add(new Point(key,prob));
        }

        while (!pq.isEmpty()){
            Point curP = pq.poll();
            if(finished[curP.point])continue;
            finished[curP.point]=true;
            probV[curP.point] = curP.prob;
            //更新距离
            if(m[curP.point]!=null) {
                for (Integer key : m[curP.point].keySet()) {
                    if (finished[key] == false) {
                        probV[key] =  Math.max(probV[key],probV[curP.point]*m[curP.point].get(key));
                        //直接往里加就行，因为往里加的大于原来的，它再里面的时候可以覆盖原来的
                        //它不在里边时，finished已经被置为true，会直接continue
                        pq.add(new Point(key,probV[key]));
                    }
                }
            }
        }
        return probV[start];
    }
}
